package com.LeeCode;

/**
 * 求一个整数的惩罚数
 */

public class Code2698 {
    public static void main(String[] args) {
        System.out.println(new Code2698().check("49", 0, 0, 7));
        System.out.println(new Code2698().punishmentNumber(37));
    }

    public int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int square = i * i;
            String num = Integer.toString(square);
            if (check(num, 0, 0, i))
                ans += square;
        }

        return ans;
    }

    private boolean check(String num, int index, int sum, int target) {
        if (index >= num.length()) return sum == target;

        for (int end = index + 1; end <= num.length(); end++) {
            int temp = Integer.parseInt(num.substring(index, end));
            boolean flag = check(num, end, sum + temp, target);
            if (flag) return true;
        }
        return false;
    }
}
